/**
 * 斐波那契数列（Fibonacci sequence）
 *
 * 斐波那契数（Fibonacci number）
 * ---------------------------------
 * 文档查看: /document/algo/fibonacci_sequence.md
 * 2021-01-18
 */

const TimeTool = require('./utils/TimeTool')

function fib1(n) {
  var fib_n = function (curr, next, n) {
    if (n == 0) {
      return curr;
    }
    else {
      return fib_n(next, curr + next, n - 1);
    }
  }
  return fib_n(0, 1, n);
}

function fib2(n) {
  if (n <= 1) return n;
  let numPre = 0;
  let numNext = 1;
  for (let i = 2; i <= n; i ++) {
    const sum = numPre + numNext
    numPre = numNext
    numNext = sum
  }
  return numNext
}

// [Done] exited with code=0 in 0.069 seconds
// 时间复杂度: O(n)
// 空间赋值度: 
TimeTool(() => {
  console.log(fib1(70));
})

// [Done] exited with code=0 in 0.066 seconds
// 时间复杂度: O(n)
// 空间赋值度: 
TimeTool(() => {
  console.log(fib2(70));
})
// 结论 fib2 优越于 fib1 



// 验证方法输出的结果是否正确: fib1
// let n = 0 // -- 0
// console.log('n=' + n, fib1(n));
// n = 1 // -- 1
// console.log('n=' + n, fib1(n));
// n = 2 // -- 1
// console.log('n=' + n, fib1(n));
// n = 3 // -- 2
// console.log('n=' + n, fib1(n));
// n = 4 // -- 3
// console.log('n=' + n, fib1(n));
// n = 5 // -- 5
// console.log('n=' + n, fib1(n));

// 验证方法输出的结果是否正确: fib2
// let n = 0 // -- 0
// console.log('n=' + n, fib2(n));
// n = 1 // -- 1
// console.log('n=' + n, fib2(n));
// n = 2 // -- 1
// console.log('n=' + n, fib2(n));
// n = 3 // -- 2
// console.log('n=' + n, fib2(n));
// n = 4 // -- 3
// console.log('n=' + n, fib2(n));
// n = 5 // -- 5
// console.log('n=' + n, fib2(n));
